import sys
import numpy as np
import heapq
from copy import copy, deepcopy
from math import ceil, floor
import cplex

class root:
    def __init__(self, mip = None):
        
        #need to organize the attributes 
        self.lp = mip
        self.rootlp = cplex.Cplex( mip )

        # convert the mip problem to lp problem
        if self.lp.get_problem_type() == 1:
            self.lp.set_problem_type(type = 0)
        elif self.lp.get_problem_type() == 0:
            print "Entered a LP program, solved at the root node"
        else : 
            print "Not processing a mip problem"
            sys.exit()

        # convert the sense to minimization here
        self.sense = self.lp.objective.get_sense()
        # 1 minimization
        # -1 minimization
        
        #self.up_bnd = self.lp.variables.get_upper_bounds()
        #self.lo_bnd = self.lp.variables.get_lower_bounds()

        self.org_up_bnds = self.lp.variables.get_upper_bounds()
        self.org_lo_bnds = self.lp.variables.get_lower_bounds()

        # indices of variables to be fixed
        self.lo_vars = []
        self.up_vars = []

        # values of the bounds
        self.lo_bnds = []
        self.up_bnds = []

        # local node info 
        self.bound = 0   # bound inherited from the parent node
        self.depth = 0   # depth in the branch and bound tree
        self.z = 0.0     # lp optimal solution
        self.bvar_ind = 0    #index of branching variable
        self.bvar_val = 0.0  #value of branching variable
        
        self.cmp_method = "depth"
        #self.cmp_method = "bound"
        self.status =""

        # global info
        if self.sense == 1: # min
            self.global_info = {'bound':1000000000,
                                'incumbent':100000000,
                                'nodecnt':1,
                                'problem':self.lp.get_problem_name()}
        else: # max
            self.global_info = {'bound':-1000000000,
                                'incumbent':-100000000,
                                'nodecnt':1,
                                'problem':self.lp.get_problem_name()}
            
        self.node_ind = self.global_info['nodecnt']

    def solve_lp(self):
        self.lp.solve()
        #update attributes of the object
 
        if self.sense == 1: # min
            self.z = ceil( self.lp.solution.get_objective_value() )
        else: #max
            self.z = floor( self.lp.solution.get_objective_value() )

#        self.z = self.lp.solution.get_objective_value()
        #heapq.heappush(self.bound_queue, self.z)

    # Another bounding options are Lagragian relaxation
    # or column generation. Both will give better bound
    # but takes more time to finish
    # def bound_by_lr(self):
    # def bound_by_cg(self):



    def fathom_by_feasibility(self):
        # infeasible
        if self.lp.solution.get_status() == 3:
            self.revert_variable_bounds()
            return True
        else:
            return False
        
    def fathom_by_optimality(self):
        x = np.array( self.lp.solution.get_values() )

        #consider the numerical issues
        for i in range(len(x)):
            if abs(x[i] - round(x[i])) < 0.000001:
                x[i] = round(x[i])

        #the efficiency can be improved here
        if not (x - np.floor(x)).any():
            # integer feasible then update the node optimal value
            # print 'fathom by optimality'
            self.status = "optimality"

            # update incumbent
            if self.sense == 1: # minimization
                self.global_info['incumbent']= min(self.z, self.global_info['incumbent'])
            else:               # maximization
                self.global_info['incumbent']= max(self.z, self.global_info['incumbent'])

            self.revert_variable_bounds()
            return True
        else:
            return False

    def fathom_by_bound(self):
        if self.z >= self.global_info['incumbent'] and \
               self.sense == 1: #minimization            
            self.revert_variable_bounds()
            return True
        elif self.z <= self.global_info['incumbent'] and \
                 self.sense == -1:  #maximization
            self.revert_variable_bounds()
            return True
        else:
            return False

    def revert_variable_bounds(self):
        #Revert the bounds before removal of each node
        if len(self.lo_vars) != 0:
            org_lo_bnds = self.rootlp.variables.get_lower_bounds(self.lo_vars)
            self.lp.variables.set_lower_bounds( zip(self.lo_vars, org_lo_bnds) )

        if len(self.up_vars) != 0:
            org_up_bnds = self.rootlp.variables.get_upper_bounds(self.up_vars)
            self.lp.variables.set_upper_bounds( zip(self.up_vars, org_up_bnds) )    

    def set_branch_var(self):
        # find the branching variable if needed
        x = np.array( self.lp.solution.get_values() )
        x_int_frac_min = np.minimum( x - np.floor(x) , np.ceil(x) - x)
        self.bvar_ind = np.argmax( x_int_frac_min )
        self.bvar_val = x[self.bvar_ind]
        #print "branching variable index", self.bvar_ind
        #print "branching variable value", self.bvar_val 
        self.revert_variable_bounds()

    # this branch method does the samething as the branch method in tree class
    def branch(self, tree):
        self.set_branch_var()
        child1 = node(self, "UP")
        child2 = node(self, "DOWN")
        heapq.heappush(tree.nodeq, child1)
        heapq.heappush(tree.nodeq, child2)


class node(root):
    # overload the constructor
    def __init__(self, parent, bdir = None):
        
        # copy parent info
        # the lists bounds
        self.lo_vars = copy(parent.lo_vars)
        self.up_vars = copy(parent.up_vars)
        self.lo_bnds=  copy(parent.lo_bnds)        
        self.up_bnds=  copy(parent.up_bnds)

        # modify global info
        self.global_info = parent.global_info
        self.global_info['nodecnt'] += 1 #increase node counts
        self.node_ind = self.global_info['nodecnt']

        # copy the lp problem
        self.lp = parent.lp
        self.rootlp = parent.rootlp
        
        # copy a few other attributes
        self.cmp_method = parent.cmp_method        
        self.bound = parent.z
        self.depth = parent.depth+1
        self.sense = parent.sense
        
        # initiate local variables
        self.z = 0.0
        self.bvar_ind = 0
        self.bvar_val = 0.0
        self.status = ""
        
        # Expand the fixed variable lists according to branching directions
        if bdir == "UP":
            #self.node_ind = parent.node_ind + 1
            self.dir = 1
            #self.lo_bnd[parent.bvar_ind] = ceil(parent.bvar_val)
            self.lo_vars.append( parent.bvar_ind )        
            self.lo_bnds.append( ceil(parent.bvar_val) )
        else:
            #self.node_ind = parent.node_ind + 2
            self.dir = -1
            #self.up_bnd[parent.bvar_ind] = floor(parent.bvar_val)
            self.up_vars.append( parent.bvar_ind )        
            self.up_bnds.append( floor(parent.bvar_val) )
            
    def __lt__(self, other):
        #compare the two objects by its depth or bound
        if self.cmp_method == "depth":
            return (self.depth, self.dir) > \
                   (other.depth, other.dir)
        elif self.cmp_method == "bound":
            return (self.bound, self.depth) > \
                   (other.bound, other.depth)                

    def solve_lp(self):
        var = self.lp.variables.get_names()
        #print "self.vars", self.vars
        #print "self.lo_bnd", self.lo_bnds
        #print "self.up_bnd", self.up_bnds

        # fix the variables
        if len(self.lo_vars) != 0:
            self.lp.variables.set_lower_bounds( zip(self.lo_vars, self.lo_bnds) )
        if len(self.up_vars) != 0:
            self.lp.variables.set_upper_bounds( zip(self.up_vars, self.up_bnds) )

        # solve the lp relaxation
        self.lp.solve()

        # record the optimal value for bounding
        self.z = self.lp.solution.get_objective_value()


#    def heur_dive_and_fix(self)
#    def heur_cut_and_fix(self)
#    def heur_relax_and_fix(self)





    
